from typing import List


class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        valueMap = {x: i for i, x in enumerate(arr)}
        ans = 0
        n = len(arr)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n - 1, -1, -1):
                if arr[j] * 2 <= arr[i]:
                    continue
                if (arr[i] - arr[j]) in valueMap:
                    k = valueMap[arr[i] - arr[j]]
                    dp[i][j] = max(dp[j][k] + 1, 3)
                    ans = max(ans, dp[i][j])
        return ans